package org.lyc.dp;

/**
 * 分割数组以得到最大和
 * https://leetcode.cn/problems/partition-array-for-maximum-sum/
 *
 * @author Liu Yicong
 * @date 2024/2/27
 */
public class HMaxSumAfterPartitioning {

	// k=3 arr1 的答案为84 数组变为 [15,15,15,9,10,10,10]
	private static int arr1[] = {1, 15, 7, 9, 2, 5, 10};

	// k=4 arr2 的答案为83 数组变为[1][7, 7, 7, 7][9, 9, 9, 9][9, 9]
	private static int arr2[] = {1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3};

	public static void main(String[] args) {
		System.out.println(maxSumAfterPartitioning(arr1, 3));
		System.out.println(maxSumAfterPartitioning(arr2, 4));
	}

	public static int maxSumAfterPartitioning(int[] arr, int k) {
		int n = arr.length;
		int[] dp = new int[n]; // dp[i] 表示: 在规则中,只考虑前i+1个元素时的最大和
		int maxValue, count;
		//遍历每个元素
		for (int i = 0; i < n; i++) {
			maxValue = 0;
			count = 0;
			dp[i] = 0;
			for (int j = i; j >= 0; j--) {
				if (arr[j] > maxValue) {
					maxValue = arr[j];
				}
				count++;
				if (count > k) {
					break;
				}
				if (j != 0) {
					dp[i] = Math.max(dp[i], dp[j - 1] + count * maxValue);
				} else {
					dp[i] = Math.max(dp[i], count * maxValue);
				}
			}
		}
		return dp[n - 1];
	}

}
